package leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
 * 说明：
 * <p>
 * 分隔时可以重复使用字典中的单词。
 * 你可以假设字典中没有重复的单词。
 * 示例 1：
 * <p>
 * 输入:
 * s = "catsanddog"
 * wordDict = ["cat", "cats", "and", "sand", "dog"]
 * 输出:
 * [
 *   "cats and dog",
 *   "cat sand dog"
 * ]
 * 示例 2：
 * <p>
 * 输入:
 * s = "pineapplepenapple"
 * wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
 * 输出:
 * [
 *   "pine apple pen apple",
 *   "pineapple pen apple",
 *   "pine applepen apple"
 * ]
 * 解释: 注意你可以重复使用字典中的单词。
 * 示例 3：
 * <p>
 * 输入:
 * s = "catsandog"
 * wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出:
 * []
 */

public class problems_140 {

    public static void main(String[] arge) {
        String s = "catsanddog";
        List wordDict = Arrays.asList(new String[]{"cat", "cats", "and", "sand", "dog"});
        System.out.println(new Solution().wordBreak(s, wordDict));
    }

    static class Solution {
        List<String> res = new LinkedList<>();

        public List<String> wordBreak(String s, List<String> wordDict) {
            dfs(s, 0, s.length(), new HashSet<>(wordDict), new boolean[s.length()], new StringBuilder());
            return res;
        }

        public void dfs(String s, int start, int length, HashSet<String> wordDict, boolean[] cantBreak, StringBuilder sb) {
            int resCurLen = res.size(); // 记录res结果的长度，如果这次DFS调用后，res多了一个String，说明这次cantBreak[start] = false,注意，这里是can't，不是can。
            if (start == length) {
                sb.deleteCharAt(sb.length() - 1);// 去掉最后一个空格
                res.add(sb.toString());
                sb.append(" "); // 补上最后一个空格，因为回溯会删掉这个空格。
            } else {
                if (!cantBreak[start]) { // cantBreak标记不能匹配的下标。也就是DFS过了，某个start开头的字符串接下去没法匹配完
                    String subString;
                    for (int end = start + 1; end <= length; ++end) {
                        subString = s.substring(start, end);
                        if (wordDict.contains(subString)) {
                            int curLen = sb.length();
                            int appendLen = subString.length() + 1;// +1 是因为每个子串后面要加个空格" "，占用一个字符位置
                            sb.append(subString).append(" ");
                            dfs(s, end, length, wordDict, cantBreak, sb);
                            sb.delete(curLen, curLen + appendLen); // 还原现场，删掉这次匹配的子串和空格，接着下次DFS
                        }
                    }
                }
                cantBreak[start] = res.size() <= resCurLen;// 这里其实是!(res.size()>resCurLen),只不过我这里cantBreak标记的是 start位置接下去“不能”完全匹配原字符串，所以写成这样。
            }
        }
    }

//    /**
//     * 遍历的方法，以下方法超时
//     */
//    static class Solution {
//        public List<String> wordBreak(String s, List<String> wordDict) {
//            List<String> ret = new ArrayList<>();
//            // 空格节点
//            Stack<Integer> spaceIndex = new Stack<>();
//            // 遍历处理
//            dfs(s, wordDict, 0, spaceIndex, ret);
//            return ret;
//        }
//        // 取得字符串部分
//        private void dfs(String s, List<String> wordDict, Integer index, Stack<Integer> spaceIndex, List<String> ret){
//            // 遍历到底
//            if(index >= s.length()){
//                StringBuffer retStr = new StringBuffer(s.length() + wordDict.size());
//                for (int i = 0; i < s.length(); i++) {
//                    if(spaceIndex.contains(i)) retStr.append(' ');
//                    retStr.append(s.charAt(i));
//                }
//                ret.add(retStr.toString());
//                return ;
//            }
//            // 遍历可用
//            for (int i = 0; i < wordDict.size(); i++) {
//                String word = wordDict.get(i);
//                // 判断是否一致
//                if ((s.length() - index) < word.length() || !word.equals(s.substring(index, index + word.length()))) continue;
//                // 处理
//                spaceIndex.push(index + word.length());
//                dfs(s, wordDict, index + word.length(), spaceIndex, ret);
//                spaceIndex.pop();
//            }
//        }
//    }

}